package 回溯;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @createTime 2023年02月28日 16:34:00
 */
public class 循环码排列1238 {
	static LinkedList<Integer> list = new LinkedList<>();

	static List<List<Integer>> result = new ArrayList<>();
	static HashSet<Integer> used = new HashSet<>();

	public static void main(String[] args) {
		System.out.println(circularPermutation(3, 2));
	}

	public static List<Integer> circularPermutation(int n, int start) {
		int max = (2 << (n - 1)) - 1;
		list.add(start);
		used.add(start);
		backTrace(max, start, 0);
		return new ArrayList<>(result.get(0));
	}

	public static void backTrace(int max, int start, int cur) {
		//结束的复合第3条件
		if (sumBinaryDiffer(start, list.getLast()).equals(1)) {
			if (list.size() == max + 1) {
				result.add(new ArrayList<>(list));
				return;
			}
		}

		for (int i = 0; i <= max; i++) {
			if (used.contains(i)) {
				continue;
			}
			//第二天剑
			if (sumBinaryDiffer(i, list.getLast()).equals(1)) {
				list.add(i);
				used.add(i);
				backTrace(max, start, i);
				list.removeLast();
				used.remove(i);
			}
		}
	}

	public static Integer sumBinaryDiffer(int a, int b) {
		int num = a ^ b;
		int diff = 0;
		while (num != 0) {
			//清除最后一个1
			num = num & (num - 1);
			diff++;
		}
		return diff;
	}
}
